Skip to main content

Insert Interval

Question​

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). Return the resulting set of intervals.

Example 1
None

Solution​

all//Insert Interval.py


# Insert Interval Algorithm
# Given a set of non-overlapping intervals and a new interval,
# insert the new interval into the existing set such that the set remains non-overlapping

# Solution:
# We will use a greedy approach to solve this problem.
# We will use two pointers start and end to keep track of the start and end of the new interval.

# Step 1: We will iterate over the intervals,
# and check if the current interval overlaps with our new interval.
# If it does, we will update the start and end pointers accordingly.

def insert_interval(intervals, new_interval):
    start, end = new_interval
    result = []
    for interval in intervals:
        if interval[1] < start:
            # no overlap
            result.append(interval)
        elif interval[0] > end:
            # no overlap
            result.append(interval)
        else:
            # overlap
            start = min(start, interval[0])
            end = max(end, interval[1])

    # add the new interval
    result.append([start, end])
    return sorted(result)